/*
https://leetcode.cn/problems/count-special-integers/
LC2376.统计特殊整数   2024.10.06 困难 通过
思路与LC1012相似
*/

class Solution {
public:
    int countSpecialNumbers(int n) {
        // 将整数n转换为字符串形式，方便按位处理
        string numStr = to_string(n);
        int len = numStr.length();

        // dp[i][mask]表示考虑前i位数字，已经使用的数字集合为mask时的方案数
        // 这里mask是一个二进制数，例如，如果mask的二进制表示中第3位为1，表示数字3已经被使用过
        // 初始化dp数组， -1表示尚未计算过
        vector<vector<int>> dp(len, vector<int>(1 << 10, -1));

        // 使用lambda表达式定义一个递归函数dfs
        // pos: 当前处理的数位位置（从左到右，从0开始计数）
        // mask: 表示已经使用过的数字集合（用二进制表示）
        // isLimit: 表示当前数位是否受到原数字n的限制，即是否只能取到n对应数位的值及以下
        // isNum: 表示前面是否已经开始组成数字（例如前面是否已经取了非0数字）
        function<int(int, int, bool, bool)> dfs = [&](int pos, int mask, bool isLimit, bool isNum) -> int {
            // 如果已经处理完所有数位
            if (pos == len) {
                // 如果已经开始组成数字（即不是前导0的情况），则返回1，表示找到了一个满足条件（数位互不相同）的数字
                // 如果还没有开始组成数字（即前面全是0），则返回0
                return isNum;
            }
            // 如果当前不是受限状态（isLimit为false）且已经开始组成数字（isNum为true）
            // 并且当前状态已经计算过（dp[pos][mask]!= -1），直接返回之前计算的结果
            if (!isLimit && isNum && dp[pos][mask]!= -1) return dp[pos][mask];

            int ans = 0;
            // 如果前面还没有开始组成数字（即isNum为false）
            if (!isNum) {
                // 不选择任何数字，直接跳到下一位进行处理，递归调用dfs
                ans = dfs(pos + 1, mask, false, false);
            }

            // 计算当前数位可以选择的数字范围
            int up = isLimit? numStr[pos] - '0' : 9;
            // 遍历当前数位可选择的数字
            for (int i = isNum? 0 : 1; i <= up; i++) {
                // 如果数字i还没有被使用过（即mask中对应的二进制位为0）
                if ((mask & (1 << i)) == 0) {
                    // 递归处理下一位数字，更新已使用数字的集合mask
                    // 如果当前数位受限且选择了最大值（isLimit && i == up），则下一位也受限
                    ans += dfs(pos + 1, mask | (1 << i), isLimit && i == up, true);
                }
            }
            // 如果当前不是受限状态且已经开始组成数字，则保存计算结果到dp数组
            if (!isLimit && isNum) dp[pos][mask] = ans;
            return ans;
        };

        // 调用dfs函数开始计算，初始状态为从第0位开始，数字集合mask为0，处于受限状态（isLimit为true），还未开始组成数字（isNum为false）
        return dfs(0, 0, true, false);
    }
};